/*
实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7
示例 2:

输入: " 3/2 "
输出: 1
示例 3:

输入: " 3+5 / 2 "
输出: 5
说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

*/

#include "stdc++.h"

/*
只用了一个数字栈。符号栈用一个变量sign代替了，只存储上一个符号，主要思想如下：
    将减法转化为加法（取相反数）
    由于乘除法优先级高，直接计算
    整数不仅一位，会>10
    表达式中没有括号
注意：
    加减乘除空格的ASCII码都小于'0'，ASCII对照表如下：http://tool.oschina.net/commons?type=4
    先做减法，避免int溢出
    char类型，不能使用switch
*/
class Solution {
public:
    int calculate(string s) {
        int result{};
        char sign{'+'};    // 上一个符号
        stack<int> nums{}; // 数字栈
        long num{0};        // temp 数字
        int n = s.size();
        int i{0};
        for (int i{0}; i < n; ++i) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + s[i] - '0';
            }
            if ((s[i] < '0' && s[i] != ' ') || (i == n - 1)) {
                // 判断前一个运算符，这样的话就把当前的运算符前面的所有数字该计算的计算，该入栈的入栈
                if (sign == '+') {
                    nums.push(num);
                } else if (sign == '-') {
                    nums.push(-num);
                } else if (sign == '*') {
                    num *= nums.top();
                    nums.pop();
                    nums.push(num);
                } else if (sign == '/') {
                    num = nums.top() / num;
                    nums.pop();
                    nums.push(num);
                }
                sign = s[i]; // 保存当前的运算符
                num = 0;
            }
        }
        // 累加数字栈中的所有数字
        while (!nums.empty()) {
            result += nums.top();
            nums.pop();
        }
        return result;
    }
};